#ifndef __SN_RBTREE_H__
#define __SN_RBTREE_H__

#include <stdint.h>
#include <sys/types.h>
#include <assert.h>

typedef struct sn_rbtree_s       sn_rbtree_t;
typedef struct sn_rbtree_node_s  sn_rbtree_node_t;

typedef void (*sn_rbtree_insert_pt) (sn_rbtree_node_t *root,
		sn_rbtree_node_t *node, sn_rbtree_node_t *sentinel);


struct sn_rbtree_node_s {
	unsigned long         key;
	sn_rbtree_node_t      *left;
	sn_rbtree_node_t      *right;
	sn_rbtree_node_t      *parent;
	u_char                color; 
	u_char                data;
};

struct sn_rbtree_s {
	sn_rbtree_node_t      *root;
	sn_rbtree_node_t      *sentinel;
	sn_rbtree_insert_pt   insert;
};
    

#define sn_rbt_red(node)               ((node)->color = 1)
#define sn_rbt_black(node)             ((node)->color = 0)
#define sn_rbt_is_red(node)            ((node)->color)
#define sn_rbt_is_black(node)          (!sn_rbt_is_red(node))
#define sn_rbt_copy_color(n1, n2)      (n1->color = n2->color)

#define sn_rbtree_sentinel_init(node)  sn_rbt_black(node)

#define sn_rbtree_init(tree, s, i)                                            \
	sn_rbtree_sentinel_init(s);                                               \
    (tree)->root = s;                                                         \
    (tree)->sentinel = s;                                                     \
    (tree)->insert = i

void sn_rbtree_insert(sn_rbtree_t *tree, sn_rbtree_node_t *node);
void sn_rbtree_delete(sn_rbtree_t *tree, sn_rbtree_node_t *node);
void *sn_rbtree_lookup(sn_rbtree_node_t * root, sn_rbtree_node_t *sentinel, unsigned long key);
void sn_rbtree_insert_value(sn_rbtree_node_t *temp, sn_rbtree_node_t *node, sn_rbtree_node_t *sentinel);
void sn_rbtree_init_insert_value(sn_rbtree_node_t *temp, sn_rbtree_node_t *node, sn_rbtree_node_t *sentinel);


#endif
